#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int SIZE = 1005, ALPHA_SIZE = 26, NOT_USED = 0, USED = 1, INF = 1000000000;
char S[SIZE];
int K;

struct Node {
    vector< int > alpha;
    int chunks;
};

void input() {
    scanf("%d%s", &K, S);
}

int cal() {
    int len = strlen(S);
    int q = len / K;
    int min_chunks = 0;
    Node base_node;
    base_node.chunks = 0;
    vector< Node > vec1d(q, base_node);
    for(int i = 0, j = 0, k = K; i < q; ++i, k += K) {
        vector< int > alpha(ALPHA_SIZE, NOT_USED);
        for(; j < k; ++j) {
            alpha[ S[j] - 'a' ] = USED;
        }
        for(int x = 0; x < ALPHA_SIZE; ++x) {
            if(alpha[x] == USED) {
                ++vec1d[i].chunks;
                vec1d[i].alpha.push_back(x);
            }
        }
        min_chunks += vec1d[i].chunks;
    }
    vector< int > vec(ALPHA_SIZE, INF);
    vector< vector< int > > vec2d(q, vec);
    if(vec1d[0].chunks == 1) {
        vec2d[0][ vec1d[0].alpha[0] ] = 1;
    } else {
        for(int i = 0, x = vec1d[0].alpha.size(); i < x; ++i) {
            vec2d[0][ vec1d[0].alpha[i] ] = vec1d[0].chunks;
        }
    }
    for(int n = 1; n < q; ++n) {
        for(int i = 0, x = vec1d[n - 1].alpha.size(); i < x; ++i) {
            for(int j = 0, y = vec1d[n].alpha.size(); j < y; ++j) {
                int next_chunks = vec2d[n - 1][ vec1d[n - 1].alpha[i] ] + vec1d[n].chunks;
                if( vec1d[n - 1].alpha[i] == vec1d[n].alpha[j]) {
                    --next_chunks;
                }
                if(vec1d[n].chunks == 1) {
                    if(vec2d[n][ vec1d[n].alpha[0] ] > next_chunks) {
                        vec2d[n][ vec1d[n].alpha[0] ] = next_chunks;
                    }
                } else {
                    for(int k = 0; k < y; ++k) {
                        if(k != j) {
                            if(vec2d[n][ vec1d[n].alpha[k] ] > next_chunks) {
                                vec2d[n][ vec1d[n].alpha[k] ] = next_chunks;
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i = 0; i < ALPHA_SIZE; ++i) {
        if(min_chunks > vec2d[q - 1][i]) {
            min_chunks = vec2d[q - 1][i];
        }
    }
    return min_chunks;
}

void output() {
    printf("%d\n", cal());
}

int main() {
    int cases;
    scanf("%d", &cases);
    while(cases--) {
        input();
        output();
    }
    return 0;
}
